Trong định nghĩa trên, giao thức là hoàn toàn đơn định và kết quả luôn chính xác. Nếu hai người được phép sử dụng các bit ngẫu nhiên và có một xác suất nhỏ tính ra kết quả sai, thì liệu họ có thể tính giá trị của f {\displaystyle f} mà chỉ cần trao đổi ít thông tin hơn nhiều trường hợp trước? Yao[1]đã trả lời câu hỏi này bằng cách đưa ra khái niệm độ phức tạp truyền thông ngẫu nhiên.

Một giao thức ngẫu nhiên R {\displaystyle R} cho hàm f {\displaystyle f} với lỗi hai mặt thỏa mãn hai điều kiện sau với mọi x và y cố định.

Pr [ R ( x , y ) = 0 ] > 1 2 , if f ( x , y ) = 0 {\displaystyle \Pr[R(x,y)=0]>{\frac {1}{2}},{\textrm {if}}\,f(x,y)=0} Pr [ R ( x , y ) = 1 ] > 1 2 , if f ( x , y ) = 1 {\displaystyle \Pr[R(x,y)=1]>{\frac {1}{2}},{\textrm {if}}\,f(x,y)=1}

Có thể xem một giao thức ngẫu nhiên và một giao thức đơn định có thêm một dữ liệu vào là một chuỗi các bit ngẫu nhiên. Có hai loại bit ngẫu nhiên khác nhau: xâu ngẫu nhiên công cộng là một xâu ngẫu nhiên cả Alice và Bob đều biết trước khi giao thức bắt đầu, trong khi xâu ngẫu nhiên riêng chỉ được cung cấp riêng cho mỗi người. Có một định lý khẳng định rằng bất kì một giao thức sử dụng xâu ngẫu nhiên công cộng nào đều có thể được giả lập bằng một giao thức sử dụng xâu ngẫu nhiên riêng với lượng bit cần trao đổi tăng thêm O(log n) bit.

Ghi chú là trong các điều kiện xác suất ở trên, kết quả chỉ phụ thuộc xâu ngẫu nhiên; cả hai xâu x và y đều nhận giá trị cố định. Nói cách khác, R(x,y) trả về giá trị g(x,y,r) khi sử dụng xâu ngẫu nhiên r, và g(x,y,r) = f(x,y) với ít nhất một nửa số giá trị của r.

Độ phức tạp ngẫu nhiên được định nghĩa là số bit cần trao đổi trong trường hợp xấu nhất của giao thức.

Cũng có thể định nghĩa giao thức ngẫu nhiên với lỗi một mặt một cách tương tự.

Giao thức ngẫu nhiên cho ví dụ EQ

Quay lại với ví dụ EQ, nếu được phép có lỗi, thì Alice và Bob có thể kiểm tra đẳng thức bằng cách trao đổi O(log n) bit. Xét giao thức sau: giả sử Alice và Bob đều biết một xâu ngẫu nhiên công cộng z ∈ { 0 , 1 } n {\displaystyle z\in \{0,1\}^{n}} . Alice tính b = z ⋅ x {\displaystyle b=z\cdot x} và gửi b cho Bob. Ký hiệu ( ⋅ ) {\displaystyle (\cdot )} là phép tính tích vô hướng trong GF(2). Sau đó Bob so sánh b với z ⋅ y {\displaystyle z\cdot y} . Nếu chúng bằng nhau, thì Bob chấp nhận, đưa ra kết quả x bằng y. Nếu không, Bob từ chối.

Rõ ràng, nếu x = y {\displaystyle x=y} , thì z ⋅ x = z ⋅ y {\displaystyle z\cdot x=z\cdot y} , nên P r o b z [ {\displaystyle Prob_{z}[} chấp nhận ] = 1 {\displaystyle ]=1} . Nếu x không bằng y, vẫn có khả năng z ⋅ x = z ⋅ y {\displaystyle z\cdot x=z\cdot y} , dẫn đến việc Bob đưa ra câu trả lời sai.

Nếu x và y khác nhau, tồn tại ít nhất một vị trí chúng khác nhau. Không mất tính tổng quát, giả sử tại vị trí thứ i, x i = 0 {\displaystyle x_{i}=0} và y i = 1 {\displaystyle y_{i}=1} . Với mọi xâu ngẫu nhiên z sao cho z ⋅ x = z ⋅ y {\displaystyle z\cdot x=z\cdot y} , xét xâu z' giống hệt như z ngoại trừ vị trí thứ i. Khi đó, z ′ ⋅ x ≠ z ′ ⋅ y {\displaystyle z'\cdot x\neq z'\cdot y} . Vì vậy P r o b z [ {\displaystyle Prob_{z}[} chấp nhận ] ≤ 1 / 2 {\displaystyle ]\leq 1/2} . Giao thức này có thể được lặp lại nhiều lần để giảm xác suất sai.

Như vậy nếu Alice và Bob có chung một xâu ngẫu nhiên công cộng n bit, họ có thể tính được E Q ( x , y ) {\displaystyle EQ(x,y)} chỉ bằng việc gửi đi 1 bit. Trong phần dưới đây, ta sẽ xét một phương pháp giả lập một giao thức dùng O(n) bit ngẫu nhiên công cộng bằng một giao thức với xâu ngẫu nhiên riêng với số bit cần trao đổi tăng thêm O(log n) bit. Như vậy, tồn tại giao thức sử dụng xâu ngẫu nhiên riêng cho EQ chỉ trao đổi O(log n) bit.

Ngẫu nhiên công cộng và riêng

Rõ ràng các bit ngẫu nhiên công cộng làm cho việc trao đổi thông tin dễ dàng hơn. Tuy nhiên, vẫn có thể sử dụng các giao thức dùng bit ngẫu nhiên công cộng ngay cả khi không có các bit này mà chỉ cần trao đổi thêm một số nhỏ bit. Mọi giao thức sử dụng n {\displaystyle n} -bit ngẫu nhiên công cộng đều có thể giả lập bằng việc trao đổi O(log n) bit.

Một cách trực giác, ta tìm một tập hợp nhỏ các xâu có đủ độ ngẫu nhiên sao cho khi thực hiện giao thức ngẫu nhiên trên tập nhỏ này, xác suất sai chỉ tăng thêm một chút. Alice và Bob có thể xác định tập hợp này trước khi thực hiện giao thức. Khi cần xâu ngẫu nhiên cho giao thức, Alice và Bob chỉ cần chọn ra một xâu trong tập hợp đó. Tập hợp này đủ nhỏ để việc xác định xâu nào được chọn chỉ đòi hỏi trao đổi một số nhỏ bit. Sau đây là chứng minh cụ thể.

Xét một giao thức P có xác suất sai không quá 0.1. Đặt R {\displaystyle R} là tập hợp 100 n {\displaystyle 100n} xâu độ dài n, ký hiệu là r 1 , r 2 , … , r 100 n {\displaystyle r_{1},r_{2},\dots ,r_{100n}} . Với một R {\displaystyle R} cho trước, định nghĩa giao thức P R ′ {\displaystyle P'_{R}} như sau: Alice chọn r i {\displaystyle r_{i}} , gửi i cho Bob, và sau đó hai người thực hiện P với xâu ngẫu nhiên công cộng là r i {\displaystyle r_{i}} . Việc gửi i đòi hỏi gửi đi O(log 100n) = O(log n) bit.

Định nghĩa p ( x , y ) {\displaystyle p(x,y)} and p R ′ ( x , y ) {\displaystyle p'_{R}(x,y)} là xác suất P {\displaystyle P} và P R ′ {\displaystyle P'_{R}} tính được kết quả đúng cho dữ liệu vào ( x , y ) {\displaystyle (x,y)} .

Xét việc chọn các xâu trong R {\displaystyle R} một cách ngẫu nhiên. Với một dữ liệu vào ( x , y ) {\displaystyle (x,y)} cố định, theo bất đẳng thức Hoeffding:

Pr R [ | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] ≤ 2 exp ⁡ ( − 2 ( 0.1 ) 2 ⋅ 100 n ) < 2 − 2 n {\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}

Khi xét tất cả mọi bộ dữ liệu ( x , y ) {\displaystyle (x,y)} :

Pr R [ ∃ ( x , y ) : | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] ≤ ∑ ( x , y ) Pr R [ | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] < ∑ ( x , y ) 2 − 2 n = 1 {\displaystyle \Pr _{R}[\exists (x,y):\,|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1}

Bất đẳng thức cuối cùng ở trên là đúng vì có 2 2 n {\displaystyle 2^{2n}} bộ dữ liệu ( x , y ) {\displaystyle (x,y)} khác nhau. Vì xác suất nhỏ hơn 1, nên tồn tại R 0 {\displaystyle R_{0}} sao cho ( x , y ) {\displaystyle (x,y)} :

| p R 0 ′ ( x , y ) − p ( x , y ) | < 0.1 {\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}

Vì P {\displaystyle P} có xác suất sai 0.1, nên P R 0 ′ {\displaystyle P'_{R_{0}}} có xác suất sai không quá 0.2.